Measurement capabilities are essential for a variety of network applications,such as load balancing, routing, fairness and intrusion detection. Thesecapabilities require large counter arrays in order to monitor the traffic ofall network flows. While commodity SRAM memories are capable of operating atline speed, they are too small to accommodate large counter arrays. Previousworks suggested estimators, which trade precision for reduced space. However,in order to accurately estimate the largest counter, these methods compromisethe accuracy of the smaller counters. In this work, we present a closed formrepresentation of the optimal estimation function. We then introduceIndependent Counter Estimation Buckets (ICE-Buckets), a novel algorithm thatimproves estimation accuracy for all counters. This is achieved by separatingthe flows to buckets and configuring the optimal estimation function accordingto each bucket's counter scale. We prove a tighter upper bound on the relativeerror and demonstrate an accuracy improvement of up to 57 times on realInternet packet traces.
展开▼
